#ifndef __BINARYTREE_H_
#define __BINARYTREE_H_

#include <iostream>

using ElementType = int;
class BinaryTree
{
public:
struct TreeNode;
    BinaryTree();
    ~BinaryTree();

    void Insert(const ElementType& element); //数据插入
    void show();

    ElementType* FindElement(const ElementType& element);

    void RemoveByElement(const ElementType &element);

    TreeNode *changeBinaryTree(TreeNode *root)
    {
        if (root == nullptr)
        {
            return nullptr;
        }

        // 交换左右子节点
        TreeNode *temp = root->left;
        root->left = root->right;
        root->right = temp;

        // 递归翻转左右子树
        changeBinaryTree(root->left);
        changeBinaryTree(root->right);

        return root;
    }

public:
    struct TreeNode //树中节点
    {
        TreeNode (const ElementType& element)
        {
            value = element;
            left = right = parent = nullptr;
        }
        ElementType value; //数据
        TreeNode * left; //左孩子
        TreeNode * right; //右孩子
        TreeNode * parent; //双亲
    };

    TreeNode* InsertNode(TreeNode* node,const ElementType& element);

    void PrevTravel(TreeNode* node);

    void MidTravel(TreeNode* node);

    void PostTravel(TreeNode* node);
    void OrderTravel(TreeNode *node);

    void FreeNode(TreeNode* node);

    TreeNode* RemoveNode(TreeNode* node,const ElementType& element);

    ElementType* FindNode(TreeNode* node,const ElementType& element);

    TreeNode* GetMinNode(TreeNode* node); //获取一个树的最小值点

    TreeNode* RotateRight(TreeNode* node);//右旋

    TreeNode* RotateLeft(TreeNode* node);//左旋

    TreeNode* RotateLeftRight(TreeNode* node);//左右旋

    TreeNode* RotateRightLeft(TreeNode *node);//右左旋

    int GetNodeHigh(TreeNode * node);//获取树高

    int LeftRightDev(TreeNode* node);//左右子树高度差

    TreeNode * root; //根节点

};


#endif